////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef binarytree_h__
#define binarytree_h__

#include "core/types.h"
#include "core/smrtptr.h"
#include "helper/array.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	BinaryTree
	///
	/// \brief	This is the simplest tree I can think of. A BinaryTree. 
	///			The BinaryTree's Node's can only have to branches and contains a value.
	///			If you want more you can either use the QuadTree oder the SimpleTree.
	///
	/// \author	khaos
	/// \date	14.12.2009
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T>
	class BinaryTree
	{
		public:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \class	Node
			///
			/// \brief	Just a Node fos this sort of containers.
			///			It contains a value and typical for a BinaryTree only two branches.
			///
			/// \author	khaos
			/// \date	14.12.2009
			////////////////////////////////////////////////////////////////////////////////////////////////////
			class Node
			{
					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	public: Node()
					///
					/// \brief	Constructor. 
					///
					/// \author	Markus
					/// \date	22.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
				public:

					Node();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node(const Node & parent, const T & element)
					///
					/// \brief	Constructor. 
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \param	[in]	parent	The parent of this Node.
					/// \param	[in]	element	The element this Node contains. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node(const Node & parent, const T & element);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	~Node()
					///
					/// \brief	Finaliser. 
					///
					/// \author	Markus
					/// \date	22.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					~Node();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void AddRef()
					///
					/// \brief	Adds a reference to this object.
					///
					/// \author	Markus
					/// \date	22.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void AddRef();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Release()
					///
					/// \brief	Releases this Node.
					///			If the internal refCount of this Node will be zero the whole Node
					///			will be destroyed.
					///
					/// \author	Markus
					/// \date	22.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Release();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	bool HasParent() const
					///
					/// \brief	Determines if this Node has a parent Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	True if there is a parent, otherwise false.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					bool HasParent() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	bool IsEmpty() const
					///
					/// \brief	Determines if this Node is empty.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	True if this Node is empty, otherwise false.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					bool IsEmpty() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Clear()
					///
					/// \brief	Clears the BinaryTree. But keep in mind that with this every Node
					///			and the value also will be deleted.
					///
					/// \author	Markus
					/// \date	22.01.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Clear();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void SetLeftBranch(const T & element)
					///
					/// \brief	Sets the value of the left branch. 
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \param	[in]	element	The element for the left branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void SetLeftBranch(const T & element);


					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void SetRightBranch(const T & element)
					///
					/// \brief	Sets the value of the right branch. 
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \param	[in]	element	The element for the right branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void SetRightBranch(const T & element);


					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void SetValue(const T & element)
					///
					/// \brief	Sets the value of this Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \param	[in]	element	The value of this Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void SetValue(const T & element);




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & Parent() const
					///
					/// \brief	Returns the parent Node.
					///			Note that here you will only have reading access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The parent Node if available, otherwise NULL.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & Parent() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & Parent()
					///
					/// \brief	Returns the parent Node.
					///			Note that you will receive full reading and writing access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The parent Node if available, otherwise NULL.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & Parent();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & LeftBranch() const
					///
					/// \brief	Returns the Node of the left branch.
					///			Note that you will only have reading access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The Node of the left branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & LeftBranch() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & LeftBranch()
					///
					/// \brief	Returns the Node of the left branch.
					///			Note that you will receive full reading and writing access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The Node of the left branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & LeftBranch();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Node & RightBranch() const
					///
					/// \brief	Returns the Node of the right branch.
					///			Note that you will only have reading access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The Node of the right branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Node & RightBranch() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node & RightBranch()
					///
					/// \brief	Returns the Node of the right branch.
					///			Note that you will receive full reading and writing access for the Node.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The Node of the right branch.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node & RightBranch();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const T & Value() const
					///
					/// \brief	Returns the value of the Node.
					///			Note that you will only have reading access for the value.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The value of the Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const T & Value() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	T & Value()
					///
					/// \brief	Returns the value of the Node.
					///			Note that you will receive full reading and writing access for the value.
					///
					/// \author	Markus
					/// \date	22.01.2010
					///
					/// \return	The value of the Node.
					////////////////////////////////////////////////////////////////////////////////////////////////////
					T & Value();

				protected:

				private:

					T m_value;

					Node * m_parentNode;

					tIndex m_refCount;

					SmrtPtr<Node> m_leftBranch;

					SmrtPtr<Node> m_rightBranch;

			};

		protected:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn BinaryTree()
			///
			/// \brief	Constructor.
			///
			/// \author	Markus
			/// \date	22.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			BinaryTree();




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const Node & Root() const
			///
			/// \brief	Returns the root of the BinaryTree.
			///			Note that you will only have reading access for the Node.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	The root Node.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const Node & Root() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Node & Root()
			///
			/// \brief	Returns the root of the BinaryTree.
			///			Note that you will receive full reading and writing access for the Node.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	The root Node.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Node & Root();

			Node  m_root;

		private:

	};





	///
	template<class T>
	BinaryTree<T>::Node::Node():
	m_refCount(0),
		m_parentNode(0)
	{

	}


	///
	template<class T>
	BinaryTree<T>::Node::Node(const typename BinaryTree<T>::Node &parent, const T &element):
	m_value(element),
		m_parentNode(&parent)
	{

	}


	///
	template<class T>
	BinaryTree<T>::Node::~Node()
	{

	}





	///
	template<class T>
	void BinaryTree<T>::Node::AddRef()
	{
		++this->m_refCount;
	}


	///
	template<class T>
	void BinaryTree<T>::Node::Release()
	{
		--this->m_refCount;

		if(this->m_refCount == 0)
			r_delete(this);
	}





	///
	template<class T>
	bool BinaryTree<T>::Node::HasParent() const
	{
		return (this->m_parentNode != NULL);
	}



	///
	template<class T>
	bool BinaryTree<T>::Node::IsEmpty() const 
	{
		return ((this->m_leftBranch == NULL) && (this->m_rightBranch == NULL));
	}


	///
	template<class T>
	void BinaryTree<T>::Node::Clear() 
	{
		this->m_leftBranch = NULL;
		this->m_rightBranch = NULL;
	}




	///
	template<class T>
	void BinaryTree<T>::Node::SetLeftBranch(const T &element)
	{
		SmrtPtr<Node> temp = r_new(Node(*this,element));

		this->m_leftBranch = temp;
	}


	///
	template<class T>
	void BinaryTree<T>::Node::SetRightBranch(const T &element)
	{
		SmrtPtr<Node> temp = r_new(Node(*this, element));

		this->m_rightBranch = temp;
	}


	///
	template<class T>
	void BinaryTree<T>::Node::SetValue(const T &element)
	{
		this->m_value = element;
	}



	///
	template<class T>
	const typename BinaryTree<T>::Node & BinaryTree<T>::Node::Parent() const
	{
		return *(this->m_parentNode);
	}


	///
	template<class T>
	typename BinaryTree<T>::Node & BinaryTree<T>::Node::Parent()
	{
		return *(this->m_parentNode);
	}


	///
	template<class T>
	const typename BinaryTree<T>::Node & BinaryTree<T>::Node::LeftBranch() const
	{
		return this->m_leftBranch;
	}


	///
	template<class T>
	typename BinaryTree<T>::Node & BinaryTree<T>::Node::LeftBranch()
	{
		return this->m_leftBranch;
	}


	///
	template<class T>
	const typename BinaryTree<T>::Node & BinaryTree<T>::Node::RightBranch() const 
	{
		return this->m_rightBranch;
	}


	///
	template<class T>
	typename BinaryTree<T>::Node & BinaryTree<T>::Node::RightBranch() 
	{
		return this->m_rightBranch;
	}


	///
	template<class T>
	const T & BinaryTree<T>::Node::Value() const
	{
		return this->m_value;
	}


	///
	template<class T>
	T & BinaryTree<T>::Node::Value()
	{
		return this->m_value;
	}





	///
	template<class T>
	BinaryTree<T>::BinaryTree()
	{

	}


	///
	template<class T>
	const typename BinaryTree<T>::Node & BinaryTree<T>::Root() const
	{
		return this->m_root;
	}


	///
	template<class T>
	typename BinaryTree<T>::Node & BinaryTree<T>::Root()
	{
		return this->m_root;
	}



}

#endif // binarytree_h__